CF559C Gerald and Giant Chess

如果没有不能走到的点,这道题就非常简单了。我们只需向下走h1h-1步,向右走w1w-1步,就可到达右下角。在这h+w2h+w-2步中,我们选h1h-1向下走,那么答案为Ch+w2h1C_{h+w-2}^{h-1}

但是,棋盘中有些点是不能走的,我们考虑用容斥原理去除多余方案,即

Ans=Ch+w2h1P1+P2+..+(1)nPnAns=C_{h+w-2}^{h-1}-P_1+P_2+..+(-1)^n * P_n

阅读全文 »

CF167E Wizards and Bets

首先,我们将所有源点与汇点筛出来,然后从每一个源点dfs求出它到各汇点的路径数,题目中保证源点与汇点数量相同,我们记为cntcnt
那么,我们可以得到一个cntcntcnt * cnt的矩阵。

先考虑路径不相交的情况(似乎大家思路都是这样),题目求的是一个排列的逆序对数,记为τ(σ)\tau(\sigma)。那么,题目等价于求:

阅读全文 »

P1769 淘汰赛制

与题目定义有些不同,nn表示人数,mm表示淘汰赛轮数。题目显然输入的是mm,根据它算出nn。为了方便2进制计算,编号从00~n1n-1。最后答案加1即可。同时,比赛胜败概率为了方便先除以100,用doubledouble计算。

现在考虑如何计算答案,设a[i][j]a[i][j]iijj的胜率,f[i][j]f[i][j]为第iijj胜出的概率。那么有:

f[i][j]=kf[i1][j]×f[i1][k]×a[j][k]f[i][j]= \sum_{k} f[i-1][j] \times f[i-1][k] \times a[j][k]

阅读全文 »

CF147B Smile House

貌似 @DDF_Van 大佬的标程过不了 , 有些题解用的二分会多一个lognlog_n,那就补一发倍增题解吧。

Solution 1

dp[s][i][j]dp[s][i][j]表示走了不多于ss条边,iji \to j的最大边权(走不通为极小值)

阅读全文 »

P2922 秘密消息

这道题还是TrieTrie树的板题,先将nn个信息插入字典树中,对于查询的密码,在字典树中查询即可。

插入很好办,我们现在来讨论查询操作。我们记s1s_1为任意一个信息,s2s_2是待匹配的密码。tot[u]tot[u]表示有多少个字符串经过点uufin[u]fin[u]表示有多少个字符串以点uu结尾。

那么会出现三种情况:

阅读全文 »

P3119 Grass Cownoisseur

我们应该用TarjanTarjan缩点,将原图变为GADGAD图,同时记录每个强连通分量的节点个数,记为num[i]num[i]

因为起点终点都是1,所以路径一定是一个环。我们可以处理出1到所有点的距离,存在dis1dis1中(跑正图)和所有点到1的距离存在dis2dis2中(跑反图)。注意,如果走不到就设为极小值。最短路跑的是点权,其实和边权差不多。

题目说可以逆向走一条有向边,我们设该边起点为uu,终点为vv,那么,答案就应为num[belong[1]]+max(dis1[v]+dis2[u])num[belong[1]]+max(dis1[v]+dis2[u])

阅读全文 »

P2341 [HAOI2006]受欢迎的牛

这道题一看就是一道强连通分量的题,不会的可以参考我的博客

当我们用TarjanTarjan缩点之后,记新图点的个数为cntcnt。我们枚举原图的每一条边,计算新图中的点的出度。对于点ii,我们把它的出度记为Out[i]Out[i]。那么,会有以下几种情况:

1.没有一个Out[i]Out[i]为0,说明每一个点至少有一条连向其他边的有向边,那么新图至少有cntcnt条边,一定会有一个环(因为cnt1cnt-1条边是一棵树,无论如何加边都会构成环),但缩点后不可能有环,矛盾。

阅读全文 »